package 中等.前缀和与差分;

/**
 * 给你一个数组 nums ，请你完成两类查询。
 * <p>
 * 其中一类查询要求 更新 数组 nums 下标对应的值
 * 另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（
 *  包含 ）的nums元素的 和 ，其中 left <= right
 * 实现 NumArray 类：
 * NumArray(int[] nums) 用整数数组 nums 初始化对象
 * void update(int index, int val) 将 nums[index] 的值 更新 为 val
 * int sumRange(int left, int right) 返回数组 nums 中索引 left 和索
 * 引 right 之间（ 包含 ）的nums元素的 和 （即，nums[left] + nums[
 * left + 1], ..., nums[right]）
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/range-sum-query-mutable
 */
public class 区域和检索数组可修改_307 {

    public static void main(String[] args) {

        int[] nums = {0, 9, 5, 7, 3};
        NumArray numArray = new NumArray(nums);
        System.out.println(numArray.sumRange(4, 4));
        System.out.println(numArray.sumRange(2, 4));
        System.out.println(numArray.sumRange(3, 3));
        numArray.update(4, 5);
        numArray.update(1, 7);
        numArray.update(0, 8);
        System.out.println(numArray.sumRange(1, 2));

    }

}

/**
 * 数状数组
 */
class NumArray {

    int[] tree;

    int[] numArray;

    // 获取到num二进制的最后一位1 如果num=2 -> 1 0 -> 1 0
    public int lowBit(int num) {
        return num & -num;
    }

    // 查询前缀和的方法
    public int query(int index) {
        int ans = 0;
        for (int curIndex = index; curIndex > 0; curIndex -= lowBit(curIndex)) {
            ans += tree[curIndex];
        }
        return ans;
    }

    // 在数状数组index位置中增加值value
    public void add(int index, int value) {
        for (int curIndex = index; curIndex < tree.length; curIndex += lowBit(curIndex)) {
            tree[curIndex] += value;
        }
    }

    public NumArray(int[] nums) {
        numArray = nums;
        tree = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            // 数组数组的索引需要从1开始
            add(i + 1, nums[i]);
        }
    }

    public void update(int index, int val) {
        add(index + 1, val - numArray[index]);
        numArray[index] = val;
    }

    public int sumRange(int left, int right) {
        return query(right + 1) - query(left);
    }

}

/**
 * 预处理+前缀和
 * 超时！！！ 虽然求和降到了O(1)的时间复杂度，但是初始化和修改都是O(n)的时间复杂度
 */
class NumArray3 {

    // sumArray[i]表示numArray中[0,i]的和
    public int[] sumArray;

    public int[] numArray;

    public NumArray3(int[] nums) {
        numArray = nums;
        sumArray = new int[nums.length];

        // 预处理前缀和
        sumArray[0] = numArray[0];
        for (int i = 1; i < nums.length; i++) {
            sumArray[i] = sumArray[i - 1] + numArray[i];
        }
    }

    public void update(int index, int val) {
        int diffVal = val - numArray[index];
        numArray[index] = val;
        // 不但会影响当前[0,index]，的总和，还会影响[0,index+1]...，后面的总和
        for (int i = index; i < sumArray.length; i++) {
            sumArray[i] += diffVal;
        }
    }

    public int sumRange(int left, int right) {
        return sumArray[right] - sumArray[left] + numArray[left];
    }

}

/**
 * 分块处理
 * 将nums分解成 一个长度为 size 的块
 * 并使用一个sum数组，记录每个size块的和
 * 求和的时间复杂度 size+n/size 当size=根号n时
 * 时间复杂度变为 2*根号n，可以视为根号n
 */
class NumArray2 {

    public int[] numArray;

    public int[] sumArray;

    public int size;

    public NumArray2(int[] nums) {
        numArray = nums;
        size = (int) Math.sqrt(nums.length);
        sumArray = new int[nums.length / size + 1];  // 可能有余数，多一个长度

        for (int i = 0, sumIndex = 0; i < numArray.length; i += size, sumIndex++) {
            for (int j = i; j < i + size && j < numArray.length; j++) {
                sumArray[sumIndex] += numArray[j];
            }
        }
    }

    public void update(int index, int val) {
        int sumIndex = ((index + 1) % size == 0 ? (index + 1) / size : (index + 1) / size + 1) - 1;
        sumArray[sumIndex] += val - numArray[index];
        numArray[index] = val;
    }

    public int sumRange(int left, int right) {
        if (left == right) {
            return numArray[left];
        }
        int sum = 0;
        int leftSumIndex = ((left + 1) % size == 0 ? (left + 1) / size : (left + 1) / size + 1) - 1;
        int rightSumIndex = ((right + 1) % size == 0 ? (right + 1) / size : (right + 1) / size + 1) - 1;

        if (leftSumIndex == rightSumIndex) {  // 左右边界在同一块中，直接遍历
            for (int i = left; i <= right; i++) {
                sum += numArray[i];
            }
            return sum;
        }

        for (int sumIndex = leftSumIndex + 1; sumIndex < rightSumIndex; sumIndex++) {
            sum += sumArray[sumIndex];
        }
        for (int i = left; i < (leftSumIndex + 1) * size; i++) {
            sum += numArray[i];
        }
        for (int i = rightSumIndex * size; i <= right; i++) {
            sum += numArray[i];
        }
        return sum;
    }

}